package com.struct.p01_sparse_array;

/**
 * @author ：qs
 * @date ：Created in 2022/4/12
 * <p>
 * 稀疏数组
 * @description：
 * @modified By：
 */

public class SparseArray {

    public static void main(String[] args) {

        // 创建一个二维数组
        int[][] arr = new int[11][11];
        arr[1][1] = 9;
        arr[3][2] = 6;
        arr[4][3] = 5;
        arr[6][1] = 13;

        // 打印二维数组
        System.out.println("初始化二维数组-------------遍历二维数组");
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                System.out.print(arr[i][j] + "   ");
            }
            System.out.println();
        }

        //二位数组----->稀疏数组
        //遍历二维数组中有效值的个数,用sum来记录
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if (arr[i][j] != 0 ){
                    sum++;
                }
            }
        }
        System.out.println("有效值个数-------------：" + sum);

        // 行数为sum+1，第一行用于保存二维数组的行列及有效值个数，列数固定为3
        int[][] sparseArr = new int[sum + 1][3];
        //存入二维数组的行列及有效值个数
        sparseArr[0][0] = arr.length;
        sparseArr[0][1] = arr.length;
        sparseArr[0][2] = sum;

        // count表示操作的sparseArr的第几行
        int count = 1;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if (arr[i][j] != 0 ){
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = arr[i][j];
                    count ++;
                }
            }
        }

        //打印稀疏数组
        System.out.println("二维数组转换为稀疏数组-------------遍历打印稀疏数组");
        for (int i = 0; i < sparseArr.length; i++) {
            for (int j = 0; j < sparseArr[0].length; j++) {
                System.out.print(sparseArr[i][j] + "   ");
            }
            System.out.println();
        }

        System.out.println("----------------------------------------");
        //稀疏数组------>二维数组
        //先得到二位数组的行列数
        int row = sparseArr[0][0];
        int col = sparseArr[0][1];
        int[][] array = new int[row][col];

        for(int i = 1; i < sparseArr.length; i++){
            row = sparseArr[i][0];
            col = sparseArr[i][1];
            array[row][col] = sparseArr[i][2];
        }
        System.out.println("稀疏数组转换为二维数组-------------遍历打印二维数组");
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[0].length; j++) {
                System.out.print(array[i][j] + "   ");
            }
            System.out.println();
        }

    }
}
